package code1.binary_tree;

/**
 * 原题链接：https://leetcode.cn/problems/maximum-binary-tree/
 */
public class P654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums,0,nums.length);
    }

    //构建子属  [begin,end)
    public TreeNode build(int[] nums,int begin,int end){
        if(begin>=end){
            return null;       //没有元素了
        }
        int max=-Integer.MAX_VALUE-1;
        int maxIndex=0;
        for(int i=begin;i<end;i++){
            if(nums[i]>max){
                max=nums[i];
                maxIndex=i;
            }
        }
        TreeNode root=new TreeNode(max);
        root.left=build(nums,begin,maxIndex);
        root.right=build(nums,maxIndex+1,end);
        return root;
    }
}
